package com.mgq.algorithm.graph;

import java.util.*;

/**
 * @author MaGuangQi
 * 拓扑排序算法
 * 程序编译用的就是拓扑算法
 * 比如 A<-B,A<-C
 * B<-C,B<-D C<-D
 * A依赖B,A依赖C,B依赖C,B依赖D
 *
 * 决定编译的顺序就是拓扑排序算法
 * 先编译D,再编译C,再编译B,再编译A
 * @date 2022-01-03 22:45
 **/
public class TopologySort {

    /**
     *  ---------
     * |        |
     * |        V
     * A->B->C->D
     * 1.先找入度为0的点.
     * 2.把A及A的影响擦掉
     * 3.剩下的图中,就会有下一个入度为0的点
     * 4.把B及B的影响擦掉
     *
     * @param graph
     */
    public List<Node> topologySort(Graph graph) {
        //map key:Node
        //    value: node的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        List<Node> result = new ArrayList<>();
        //保存入度为0的node
        Queue<Node> zeroQueue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            //把node的入度依次加入到map中
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroQueue.add(node);
            }
        }
        while (!zeroQueue.isEmpty()) {
            Node zeroNode = zeroQueue.poll();
            //打印
//            System.out.println(zeroNode.value);
            result.add(zeroNode);
            //把0入度的节点和节点的影响擦掉(想想编译的例子,已经开始编译我了,那么对我依赖的就可以擦掉)
            for (Node next : zeroNode.nexts) {
                //把我邻节点的入度-1
                inMap.put(next,inMap.get(next)-1);
                //减完之后,会有某个node的入度又为0了
                if (inMap.get(next) == 0) {
                    zeroQueue.add(next);
                }
            }
        }
        return result;
    }
}
